#include<vector>
#include<iostream>
#include<algorithm>
using std::max;
using std::vector;


class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int maxNum = nums[0];
        for (auto& n: nums) {
            sum += n;
            maxNum = max(maxNum, n);
        }
        if (sum % 2 == 1 || nums.size() < 2 || maxNum > sum/2) return false;
        int n = nums.size();
        int target = sum / 2;
        // dp[v] 代表前i个数 最大约束v的情况下组成的max value
        
        vector<bool> dp(target+1, false);
        // 初始值
        dp[0] = true;
        dp[nums[0]] = true;
        for (int i = 1; i < n && !dp[target]; i++) {
            int num = nums[i];
            for (int v = target; v >= num; v--) {
                dp[v] = dp[v] || dp[v-num];
            }
        }
        return dp[target];

    }
};